#include "../tools.h"


class Cmp{
public:
    bool operator()(const pair<string,int>& a, const pair<string,int>&b){
        if(a.second != b.second) return a.second > b.second;
        else return a.first < b.first;
    }
};

class Solution {
public:
    vector<string> topKFrequent(vector<string>& words, int k) {
        unordered_map<string,int> dict;
        for(auto& e: words){
            if(dict.find(e) != dict.end()) ++dict[e];
            else dict[e] = 1;
        }

        priority_queue<pair<string,int>, vector<pair<string,int>>, Cmp> qMin;
        for(auto& e: dict){
            if(qMin.size() < k) qMin.push(e);
            else {
                auto top_e = qMin.top();
                if(top_e.second < e.second){
                    qMin.pop();
                    qMin.push(e);
                }
            }
        }

        vector<string> res(k);
        for(int i = k - 1; i >= 0; --i){
            res[i] = qMin.top().first;
            qMin.pop();
        }
        return res;
    }

};


int main(int argc, char const *argv[])
{
    Solution sol;

    vector<string> words = {"the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"};
    int k = 4;

    vector<string> res = sol.topKFrequent(words, k);
    for(auto& e: res)
        cout << e << " ";
    


    return 0;
}
